1. Technical Field
This invention relates to parallel processing systems and, in particular, to outer product processors capable of solving linear programming problems.
2. Discussion
Linear programming is an application of linear algebra that has been developed within the last 40 years as a technique for economic planning and decision making. Stated concisely, a central problem of management is to utilize available resources for the production of goods and the provision of services in such a way that specified objectives are achieved in the best possible manner. The available resources can include raw materials, labor supply, energy resources, planned capacity, and distribution methods among others. Goods and services can include manufactured products, agricultural output, transportation and communication, as well as health care and other needs of society. A specific objective of management might be to maximize employment or profit or production or to minimize costs or delivery time or fuel consumption. Executing such activity typically is subject to various quantitative constraints, such as a limited supply of raw materials, skilled workers, or machine capacity. Constraints can also be imposed by contractual agreements and standards of quality of the finished products.
The above problems can frequently be expressed as a linear programming problem in the following form: ##EQU1## Feasible regions of the above problem define a convex polyhedron; the problem then is to find the point on the convex polyhedron where the function assumes its maximum (or minimum) value.
The field of linear programming was essentially created in 1946, when G. B. Dantzig defined its scope and proposed the first, and still most widely used, method for the practical solution of linear programming problems, called the Simplex method. Currently, the most common linear programming codes are careful "sparse" implementations of the so-called revised Simplex method and, more recently, of the barrier (Karmarkar) interior point method.
In business, the most common linear programming problems share common features (sparsity, structure) and usually need not be solved in real time. However, linear programming is also applicable to many problems in robotics (motion planning, computer vision), industry (navigation and onboard computing, dynamic resource allocation), and tactical business decisions (stocks and other in-time business decisions). These problems, although typically smaller (in terms of constraints and variables) than the former type of linear programs, often are dense and need to be solved in a "real" time.
The revised Simplex method and, more recently, the barrier, (Karmarkar) interior point method are capable of solving some very large (in terms of dimensions) linear programs in the course of several hours. The linear programs so solved, are invariably sparse and structured, which allows for the numerous time saving heuristics that are used. However, without the sparsity, even the moderately sized problems are often intractable in the required amount of time. Thus, it would be desirable to provide a system and method for solving dense linear programming problems that are in real time.
Also, current procedures for solving linear programming problems typically involve signals that are propagated sequentially. Due to the large number of steps required to solve many liner programming problems, it would be desirable to provide a system to perform linear programming processing in parallel rather than sequentially.